/*
二分查找，也称为折半查找，是一种高效的查找算法，适用于已经排序的数组。
它通过比较中间值和目标值，逐步缩小查找范围，
从而加快查找速度。以下是C语言中二分查找的实现示例：
*/



#include <stdio.h>

// 二分查找函数
int binarySearch(int arr[], int size, int target) {
    int left = 0;  // 左边界
    int right = size - 1;  // 右边界

    while (left <= right) {
        int mid = left + (right - left) / 2;  // 计算中间索引

        if (arr[mid] == target) {
            return mid;  // 找到目标值，返回索引
        } else if (arr[mid] < target) {
            left = mid + 1;  // 目标值在右半部分
        } else {
            right = mid - 1;  // 目标值在左半部分
        }
    }

    return -1;  // 未找到目标值
}

int main() {
    int arr[] = {1, 3, 5, 7, 9, 11, 13, 15, 17};  // 已排序的数组
    int size = sizeof(arr) / sizeof(arr[0]);  // 数组大小
    int target = 7;  // 目标值

    int result = binarySearch(arr, size, target);

    if (result != -1) {
        printf("找到目标值 %d, 索引是: %d\n", target, result);  // 输出找到的结果
    } else {
        printf("未找到目标值 %d\n", target);
    }

    return 0;
}


/*
代码解读
参数：arr是已排序的数组，size是数组大小，target是要查找的目标值。
循环：在循环中，通过计算中间索引 mid，比较 arr[mid] 和 target 的关系。
调整边界：如果 target 大于中间值，则调整左边界 left；如果 target 小于中间值，则调整右边界 right。
终止条件：当 left 超过 right 时，查找结束，未找到目标值。
注意事项
二分查找的前提是数组必须排序。如果数组未排序，需要先进行排序。
二分查找适用于静态数组，对于动态变化的数据结构，可能需要其他查找算法。
计算中间索引时，left + (right - left) / 2 的写法可以防止整数溢出
*/
